class Solution:
  def permutation(self, s: str) -> list:
    from copy import deepcopy
    if not s:
      return []
    res = list()
    s_list = [i for i in s]
    def dfs(level: int, cur_path: list):
      # print('dfs(level={}, cur_path={})'.format(level, cur_path))
      if level == len(s):
        res.append(cur_path)
        return
      # 剩余可选项
      choices = deepcopy(s_list)
      for traversed in cur_path:
        choices.remove(traversed)
      # 遍历剩余可选项
      for choice in choices:
        cur_path.append(choice)
        dfs(level + 1, cur_path[:])
        cur_path.pop()
    # 遍历第一项
    for i in range(len(s_list)):
      dfs(1, [s_list[i]])
    # 对最终结果进行处理，每个列表都转换为字符串
    for i in range(len(res)):
      res[i] = ''.join(res[i])
    return list(set(res))


'''
STATUS: SOLVED
TRIES:  2
TIME:   2012 MS
MEMORY: 22.8 MB
'''
if __name__ == "__main__":
  solution = Solution()
  print(solution.permutation('aa'))
